package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.递归;

import com.zp.self.module.level_4_算法练习.数据结构.二叉树.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_897_递增顺序搜索树 {
    @Test
    public void main() {

        Solution solution = new 力扣_897_递增顺序搜索树().new Solution();
        System.out.println();
    }

    /**
     * 题目：给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，
     * 使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
     *
     * 示例 1：
     * 输入：root = [5,3,6,2,4,null,8,1,null,null,null,7,9]
     * 输出：[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]
     *
     * 示例 2：
     * 输入：root = [5,1,7]
     * 输出：[1,null,5,null,7]
     *
     * 分析：【P 💖💖】
     * 1.深度优先：遍历节点存储到List，使用res哑元节点，记录要返回的节点
     *          --执行耗时: 0 ms,击败了100% 的Java用户
     *          --编码耗时：[57:53]
     *
     * 边界值 & 注意点：
     * 1.
     **/
//leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public TreeNode increasingBST(TreeNode root) {
            List<TreeNode> list =new ArrayList<>();
            dsf(root,list);
            TreeNode res = new TreeNode(),pro=res;
            for (TreeNode treeNode : list) {
                pro.right=treeNode;
                pro=treeNode;
            }
            return res.right;
        }

        private void dsf(TreeNode root, List<TreeNode> list) {
            if(root.left!=null)
                dsf(root.left,list);
            root.left=null;
            list.add(root);
            if(root.right!=null)
                dsf(root.right,list);
            root.right=null;
        }
    }


//leetcode submit region end(Prohibit modification and deletion)

}